// https://www.lintcode.com/problem/maximum-product-subarray/

public class Solution {
    /**
     * @param nums: An array of integers
     * @return: An integer
     */
    public int maxProduct(int[] nums) {
        // write your code here
        int ret = nums[0];
        int[] maxProducts = new int[nums.length]; // 两个数组方便处理负值
        int[] minProducts = new int[nums.length];
        Arrays.fill(maxProducts, 0);
        Arrays.fill(minProducts, 0);
        maxProducts[0] = nums[0];
        minProducts[0] = nums[0];
        for (int i = 1; i < nums.length; ++i) {
          maxProducts[i] = Math.max(maxProducts[i - 1] * nums[i], minProducts[i - 1] * nums[i]);
          maxProducts[i] = Math.max(maxProducts[i], nums[i]);
          minProducts[i] = Math.min(maxProducts[i - 1] * nums[i], minProducts[i - 1] * nums[i]);
          minProducts[i] = Math.min(minProducts[i], nums[i]);
          if (maxProducts[i] > ret) {
            ret = maxProducts[i];
          }
        }
        return ret;
    }
}